﻿#https://www.luogu.com.cn/problem/P10426
洛谷：


在一个神秘的森林里，住着一个小精灵名叫小蓝。有一天，他偶然发现了一个隐藏在树洞里的宝藏，里面装满了闪烁着美丽光芒的宝石。这些宝石都有着不同的颜色和形状，但最引人注目的是它们各自独特的 “闪亮度” 属性。每颗宝石都有一个与生俱来的特殊能力，可以发出不同强度的闪光。小蓝共找到了 n 枚宝石，第 i 枚宝石的 “闪亮度” 属性值为 H
i
​
，小蓝将会从这 n 枚宝石中选出三枚进行组合，组合之后的精美程度 S 可以用以下公式来衡量：

S = H
a
​
H
b
​
H
c
​
⋅
LCM(H
	a
	​
	, H
	b
	​
)⋅LCM(H
	a
	​
	, H
	c
	​
)LCM(H
	b
	​
	, H
	c
	​
)
LCM(H
	a
	​
	, H
	b
	​
	, H
	c
	​
)
​

其中 LCM 表示的是最小公倍数函数。

小蓝想要使得三枚宝石组合后的精美程度 S 尽可能的高，请你帮他找出精美程度最高的方案。如果存在多个方案 S 值相同，优先选择按照 H 值升序排列后字典序最小的方案。

输入格式
第一行一个整数 n 表示宝石个数。
第二行有 n 个整数 H
1
​
, H
2
​
, …H
n
​
表示每个宝石的闪亮度。

输出格式
输出一行包含三个整数表示满足条件的三枚宝石的 “闪亮度”。

输入输出样例
输入 #1复制
5
1 2 3 4 9
输出 #1复制
1 2 3
说明 / 提示
数据规模与约定
对 30 % 的数据，n≤100，H
i
​
≤10
3
。
对 60 % 的数据，n≤2×10
3
。
对全部的测试数据，保证 3≤n≤10
5
，1≤H
i
​
≤10
5
。



//结论就是找三个数；他们的最大因数（S）最大；如果最大公因数都相同找最小的那三个

//整体思路：首先拿到数组中所有的因数然后统计他们个数+筛选出cnt最大的因数（即最大公因数）；然后拿着最大公因数对原数组从小到大遍历出前三个
#include<bits/stdc++.h>
#define opze ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int n;
vector<int>data;
const int N = 1e5 + 1;
int cnt[N] = { 0 };//cnt[i]表示除i能除尽的数的个数
void solve() {
    //输入一个统计一个；找到1-它的因数
    cin >> n;
    data.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> data[i];
        int x = data[i];
        for (int j = 1; j <= sqrt(x); j++) {
            //找因数只用看一半（不过另一半要特殊处理放入cnt）
            if (x % j == 0) {
                if (j * j != x) cnt[x / j]++;
                //比如x=12统计了因数3；之后还会有个4因此这里特殊判断一下；如果是9；
                //3 3这种结果就要忽略防止多加1次
                cnt[j]++;
            }

        }
    }
    //拿到公因数数组；找到最大公因数tar：
    int tar = 0;
    for (int i = N; i >= 1; i--) {
        if (cnt[i] >= 3) {
            tar = i;
            break;
        }
    }
    //为的是如果有多组都是同一个公因数直接拿到最小的三个
    sort(data.begin(), data.end());
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (data[i] % tar == 0) { cout << data[i] << " "; count++; }
        if (count == 3) break;
    }

}
int main() {
    solve();
    return 0;
}